/*
练习15-3 旅行商问题
分数 30
作者 陈越
单位 浙江大学

旅行商需要到若干城市去推销商品，已知各城市间的旅费，要求找到一条从驻地出发，经过每个城市仅一次，最后回到驻地的路线，使总旅费最少。请设计分支限界算法解决这个问题。
函数接口定义：

int TSP( MGraph graph );

其中 MGraph 类型的定义如下：

typedef int Vertex;    //  顶点编号类型
typedef int GElemSet;  //  边权重类型
typedef struct MGraphNode *MGraph; //  邻接矩阵表示的图
struct MGraphNode {
    int n_verts; //  顶点数
    int m_edges; //  边数
    GElemSet **edge_matrix;//  邻接矩阵
    GElemSet no_edge_value; //  表述没有边时的权重值
    bool directed; //  true为有向图，false为无向图
};

题目保证传入的图 graph 不超过 10 个顶点，no_edge_value 取值为 109。要求函数 TSP
返回旅行商问题的最小费用。如果根本不存在周游路线，则返回 0。
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex;                /* 顶点编号类型 */
typedef int GElemSet;              /* 边权重类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts;            /* 顶点数 */
    int m_edges;            /* 边数 */
    GElemSet **edge_matrix; /* 邻接矩阵 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed;          /* true为有向图，false为无向图 */
};
#define NIL -1 /* 空顶点编号 */
#define kMaxV 10
#define infinity (1e9)

MGraph BuildGraph(); /* 创建图的代码由裁判实现 */
int TSP(MGraph graph);

int main(void) {
    MGraph graph;

    graph = BuildGraph();
    printf("%d\n", TSP(graph));

    return 0;
}

/* 你的代码将被嵌在这里 */

void TSPHelper(MGraph graph, int pos, int cost, int *path, int *visited, int *minCost) {
    // 如果已经访问了所有顶点
    if (pos == graph->n_verts) {
        // 检查最后一个顶点是否能回到起点
        if (graph->edge_matrix[path[pos - 1]][path[0]] != graph->no_edge_value) {
            // 更新最小费用
            if (cost + graph->edge_matrix[path[pos - 1]][path[0]] < *minCost) {
                *minCost = cost + graph->edge_matrix[path[pos - 1]][path[0]];
            }
        }
        return;
    }
    // 尝试访问每一个顶点
    for (int i = 0; i < graph->n_verts; i++) {
        // 如果顶点未被访问且存在边
        if (visited[i] == 0 && graph->edge_matrix[path[pos - 1]][i] != graph->no_edge_value) {
            visited[i] = 1; // 标记顶点已访问
            path[pos] = i;  // 更新路径
            // 递归访问下一个顶点
            TSPHelper(graph, pos + 1, cost + graph->edge_matrix[path[pos - 1]][i], path, visited, minCost);
            visited[i] = 0; // 回溯，标记顶点未访问
        }
    }
}

int TSP(MGraph graph) {
    int n = graph->n_verts;
    int minCost = infinity; // 初始化最小费用为无穷大
    int *path = (int *)malloc(n * sizeof(int)); // 分配路径数组
    int *visited = (int *)malloc(n * sizeof(int)); // 分配访问标记数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化访问标记数组
    }
    visited[0] = 1; // 标记起点已访问
    path[0] = 0; // 起点为0
    // 调用辅助函数进行递归搜索
    TSPHelper(graph, 1, 0, path, visited, &minCost);
    free(path); // 释放路径数组
    free(visited); // 释放访问标记数组
    // 如果最小费用仍为无穷大，表示不存在周游路线，返回0；否则返回最小费用
    return (minCost == infinity) ? 0 : minCost;
}